\documentclass[a4paper,14pt]{extreport}

\usepackage{bachelor}
\usepackage{algorithmic} % псевдокод
\usepackage{listings}
\lstset{language=C++, texcl=true, frame=lines, basicstyle=\ttfamily}  % latex в комментариях 

%opening
\begin{document}

\title{Моделирование динамических процессов на регулярных решетках с использованием графических ускорителей}
\author{А. С. Мордвинцев}
\date{\today}


\sloppy  % предпочитать растяжение пробелов заползанию текста на поля

\maketitle

\setcounter{page}{3}

\tableofcontents

\include{intro}

\include{voxel}

\chapter{Визуализация воксельного октарного дерева методом обратной трассировки лучей}

В рамках написания данной работы было разработано приложения, позволяющие визуализировать трехмерную сцену, представленную воксельным октарным деревм, и вносить в нее изменения в интерактивном режиме. В данной главе описаны детали его реализации.

\section{Машинное представление данных сцены}

В процессе своей работы данное приложение поддерживает два копии данных сцены. Одна из копий располагается в оперативной пямяти компьютера, доступной центральному процессору, и ипользуется для внесения редактирования сцены. Другая копия располагается в памяти видеокарты и используется для визуализации. Обе копии представляют собой идентичные структуры данных -- линейный массив структура типа \texttt{VoxNode}. Ниже приведено описание данной структуры на язке C++.

\begin{lstlisting}[caption={Структура ноды воксельного дерева}]

typedef uint VoxData; // color - 16bit, normal - 16bit
typedef uint VoxChild; // VoxData or VoxNodeId
typedef uint VoxNodeInfo; //  0 .. 7   - leafFlags, 
                          //  8 .. 15  - nullFlags, 
                          // 19     - emptyFlag
typedef uint VoxNodeId;

#pragma pack(push, 4)  
struct VoxNode
{
  VoxNodeInfo flags;
  VoxData     data;
  VoxChild    child[8];
};
#pragma pack(pop)

const VoxNodeId EmptyNode = 0x80000000;
const VoxNodeId FullNode  = 0x80000001;
\end{lstlisting}

	Каждая нода дерева содержит:
\begin{itemize}
\item слово битовых флажков, 8 из которых сообщают, является ли каждая из полей типа VoxChild ссылкой на дочернюю ноду или непосредственно данные вокселя (\texttt{VoxData});
\item поле типа \texttt{VoxData}, содержащее представление всего поддерева с корнем в данном узле на более грубом уровне детализации; в данной работе цвет и нормаль, упакованные в данное поля вычисляются как среднее арифметическое цветов и нормалей всех вокселей поддерева;
\item 8 полей, каждое из которых может быть либо индексом дочернего узла дерева в линейном массиве, либо данными вокселя, либо, если старший бит поля установлен в 1, специальным значением, сообщеющим, что данное поддерево лежит целиком внутри, либо снаружи объекта, и его хранение не представляет смысла.
\end{itemize}

Тип \texttt{VoxData} представляет собой квантованный 16-битный цвет и 16-битную, квантованную методом, описанным в статье \cite{quant_normals}, нормаль. 

Для повышения производительности чтение данных из линейного массива CUDA ядром выполняются при помощи запросов к одномерной текстуре, которые, в отличие от простых чтений из глобальной памяти, кешируются.

Для добавления и удаления произвольных элементов в массив, хранящиейся в пямяти CPU, используется простой менеджер памяти, оперирующий элементами одинакового размера и поддерживающий односвязный список свободных элементов массива.

Массив узлов дерева разбит на страницы по 256 элементов. Для каждой страницы хранится номер ее версии, который обновляется при модификации любого элемента страницы. Этот механизм позволяет отслеживать изменившиеся участки массива для выборочной пересылки в пямять GPU для синхронизации двух копий представления сцены. Размер страницы был подобран опытным путем и обеспечивает компромис между количеством операций, иницирующих пересылку данных, и самим объемом пресылаемых при внесении изменений в сцену данных.

\section{Архитектура приложения}
На рис.~\ref{fig:trace_comp_relation} показаны основных компоненты разработанного воксельного приложения. Серым цветом показаны компоненты, взаимодействующие с видеокартой при помощи CUDA.

\begin{figure}[h]
\center
\includegraphics[width=\textwidth]{trace_comp_relation.pdf}
\caption{Основные компоненты тестового приложения. Серым цветом выделены компоненты, использующие CUDA}
\label{fig:trace_comp_relation}
\end{figure}

Остановимся подробнее на функциях показанных компонентов.

\begin{itemize}
\item \texttt{HomoStorage<T>} перставляющий собой пул однородных элементов, поддерживающий аллокацию нового элемента, удаление произвольного элемента и контроль и обновление версий страниц элементов.

\item \texttt{VoxelSource} представляет собой интерфейс, который реализеутся в тестовом приложении такими объектами, как \texttt{RawSource}, \texttt{SphereSource} и \texttt{IsoSource}. Каждый из них является исаточником воксельных данных, либо процедурным, либо преобразующим данные из какого-либо внешнего формата. Экземпляры объектов, реализующих данный интерфес, передаются объекту класса \texttt{DynamicSVO} для выполнения опреаций редактирования сцены. Основным методом интрерфейса является метод \texttt{TryRange}, который получает на вход позицию, размеры и уровень детализации кубической области пространства, и возвражает один из следующих результатов:
\begin{itemize}
\item участок пуст;
\item участок целиком содержится внутри объекта;
\item участок является вокселем поверхности, в этом случае возвращаются его свойства;
\item участок может быть неоднородным, требуется дальнейшее разбиение.
\end{itemize}

\item \texttt{DynamicSVO} реализует операции по редактированию воксельной сцены. Поддерживаются операции вычитания и объединения объемов, получаемых через интерфейс \texttt{VoxelSource}, с текущей сценой. Также компонент поддерживает номер версии данных, и обновляет версии страниц в \texttt{HomoStorage<T>}.

\item \texttt{CudaSVO} отвечает за хранение копии сцены в памяти GPU и эффективную синхронизацию этой копии с оригиналом в основной памяти.

\item \texttt{SVORenderer} отвечает за GPU визуализацию воксельной сцены. Устанавлнивает параметры работы CUDA-ядер, поддерживает необходимые буферы и структуры данных, запускает вычисления на GPU.

\item \texttt{Demo} -- основной компонент приложения. Координирует работу всех остальных компонентов, обеспечивает взаимодействие с пользователем.

\end{itemize}


\section{Сокрытие артефактов вокселизации}

Так как вся сцена, при использовании данного подхода, представляет собой множество кубических вокселей, они становятся очень заметны, когда наблюдатель находится радом с коверхностью какого-либо объекта. Для борьбы с этим явлением в данной работе были примены два следующих приема:
\begin{itemize}
\item к начальной позиции каждого трассируемого луча прибавляется случайное смещение, размер которого сравним с размером вокселя,
\item в моменты времени, когда сцена на экране остается неизменной, производится усреднение значений цветов нескольких последовательных кадров, отрисованных с разными отклонениями начальных позиций лучей.
\end{itemize}
Эти два приема приводят к тому, что близкие к наблюдателю воксели отображаются ввиде расплывчатых пятен, похожих на эффект фокального размытия, встречающися в фотографии. Примеры работы этих техник можно увидеть на рис.~\ref{fig:voxel_blur}.

\begin{figure}[h]
  \begin{center}
    \subfigure[Без сокрытия]{\label{fig:blur-a}\includegraphics[width=.45\textwidth]{trace_blur1.jpg}}
    \subfigure[Со случайными смещениями начальных точек лучей]{\label{fig:blur-b}\includegraphics[width=.45\textwidth]{trace_blur2.jpg}} \\
    \subfigure[Усредненное по нескольким кадрам изображение]{\label{fig:blur-c}\includegraphics[width=.7\textwidth]{trace_blur3.jpg}}
  \end{center}
  \caption{Сокрытие артефактов вокселизации}
  \label{fig:voxel_blur}
\end{figure}

\include{svo_trace}

\chapter*{Заключение}
\addcontentsline{toc}{chapter}{Заключение}

Основной вклад данной работы заключается в демонстрации применимости структуры данных разреженное октарное воксельное дерево (SVO) в приложениях интерактивной трехмерной графики. Реализован алгоритм обратной трассировки лучей на SVO, использующий технологию NVIDIA CUDA для переноса вычислений на современные графические ускорители. Достигнута производительность в 20-40 кадров в секуду в зависимости от сложности сцены на видеокарте NVIDIA GeForce GTX 275 в разрешении 1024х768. Исследована эффективность работы встроенного планировщика заданий GPU, показано, что его работа в данном приложении не является оптимальной и даны рекомендации по дальнейшему усовершенствованию трассировщика. В качестве источника сложной геометрии была реализована полип-ориентированная модель роста коралла.	

Описанные методы представления сцены и визуализации применимы в широком спектре приложений, работающих с динамически изменяющимися трехмерными объектами. Примерами таких являются программы математического моделирования процессов эрозии или агрегации, пакеты трехмерного моделирования, реализующие техники виртуального скульптурирования, а также хирургические симуляторы.


\appendix
\renewcommand{\appendixname}{Приложение}
\include{app}

\include{bibl}


\end{document}
